package a07_二叉树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;


public class a04_二叉树的统一迭代法 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3, null, null), null));
//        TreeNode treeNode = new TreeNode(1, null, null);
        List<Integer> list = inorderTraversal(treeNode);
        System.out.println(list);

    }

    //前序 中左右
    //          1
    //     2          3
    //  4     5    6      7
    //预期结果：1,2,4,5,3,6,7
    //stack: 1

    //1、
    //stack:3,2,1,null
    //result:

    //2、
    //stack:3,2
    //result:1

    //3、
    //stack:3,5,4,2,null
    //result:1

    //4、
    //stack:3,5,4
    //result:1,2

    //5、
    //stack:3,5,4,null
    //result:1,2

    //6、
    //stack:3,5
    //result:1,2,4

    //7、
    //stack:3,5,null
    //result:1,2,4

    //8、
    //stack:3
    //result:1,2,4,5

    //9、
    //stack:7,6,3,null
    //result:1,2,4,5

    //10、
    //stack:7,6
    //result:1,2,4,5,3
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            //规定：stack里面要处理的元素后面用null进行标识
            if(stack.peek() != null){//继续遍历
                TreeNode popNode = stack.pop();//下面要添加右左中，这里为了避免重复，直接将中去除

                if (popNode.right != null) {
                    stack.add(popNode.right);//右
                }
                if (popNode.left != null) {
                    stack.add(popNode.left);//左
                }
                stack.add(popNode);//中
                stack.add(null);// 中节点访问过，但是还没有处理，加入空节点做为标记。
            }else {//碰到null了，需要处理了
                stack.pop();
                TreeNode popNode = stack.pop();
                result.add(popNode.val);
            }
        }
        return result;
    }

    //中序：左中右
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            if(stack.peek() != null){
                TreeNode popNode = stack.pop();

                if (popNode.right != null) {
                    stack.add(popNode.right);
                }
                stack.add(popNode);
                stack.add(null);

                if (popNode.left != null) {
                    stack.add(popNode.left);
                }
            }else {
                stack.pop();
                TreeNode popNode = stack.pop();
                result.add(popNode.val);
            }
        }

        return result;
    }

    //后序 左右中
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            if (stack.peek() != null) {
                TreeNode popNode = stack.pop();

                stack.add(popNode);
                stack.add(null);

                if (popNode.right != null) {
                    stack.add(popNode.right);
                }

                if (popNode.left != null) {
                    stack.add(popNode.left);
                }
            }else {
                stack.pop();
                TreeNode popNode = stack.pop();
                result.add(popNode.val);
            }
        }
        return result;
    }


}
